// This is unpublished source code. Michah Lerner 2006

package trieMatch.keywordMatcher;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

import trieMatch.Constants;
import trieMatch.Interfaces.MapFactory;
import trieMatch.Interfaces.Similarity;

/**
 * Implementation retrieves the <strong>EXP</strong> matching criterion (prefix with lookahead support). The internal
 * setting <code>earlyExitOnExactMatch</code> can be set, so that matched tokens won't do prefix lookups. <strong>This
 * matcher must have a TreeSet for good performance</strong>, as gets automatically configured by the driver programs.
 * <B>NOTE:</B> THIS ASSUMES AND REQUIRES THAT TREESET IS USED. OTHERWISE, USE THE ALTERNATE findPrefixesA GIVEN BELOW
 * 
 * @author Michah.Lerner
 * 
 */

public class SortedtrieMatchEXP extends TrieMatcher {
	static boolean earlyExitOnExactMatch = false;
	@SuppressWarnings("hiding")
	Similarity similarity = new ResultScorer_prefixPhrase();

	@Override
	public MapFactory mapFactory() {
		class mapFactory implements MapFactory {
			public Map<String, Tiers> newMap() {
				return new TreeMap<String, Tiers>();
			}
		}
		return new mapFactory();
	}

	public SortedtrieMatchEXP() {
		super();
	}

	public SortedtrieMatchEXP(final Tiers tiers) {
		super(tiers);
	}

	public SortedtrieMatchEXP(final Tiers tiers, final Sequencer sequencer) {
		super(tiers, sequencer);
	}

	@Override
	List<KMDefinition> findMaxMatch(final Tiers current, final int pos) {
		if (pos >= lookingFor.size()) { return current.instances != null
				? validForMatchtype(current.instances)
				: emptyMatchable; }
		final Collection<Map.Entry<String, Tiers>> prefixMaps = findPrefixesB(current.successors, lookingFor.get(pos).getValue());
		if (prefixMaps != null) {
			final List<KMDefinition> nList = new ArrayList<KMDefinition>();
			final List<KMDefinition> v2 = findMaxMatch(current, pos + 1);
			nList.addAll(v2);
			if (nList.size() <= Constants.maxInternalResults) {
				for (final Map.Entry<String, Tiers> me : prefixMaps) {
					// INLINED: final List<KMDefinition> v1 = findMoreMaxMatch(me.getValue(), pos);
					depthStack.push(pos);
					final List<KMDefinition> v1 = findMaxMatch(me.getValue(), pos + 1);
					depthStack.pop();

					nList.addAll(v1);
					if (nList.size() > Constants.maxInternalResults) {
						break;
					}
				}
			}
			return nList;
		}
		return findMaxMatch(current, pos + 1);
	}

	@Override
	public float sim(final StructuredElement element, final String description) {
		return similarity.sim(element, description);
	}

	/**
	 * TreeSet prefix lookup (faster)
	 * 
	 * @param current
	 * @param name
	 * @return matched entries
	 */
	@SuppressWarnings("unchecked")
	Collection<Map.Entry<String, Tiers>> findPrefixesB(final Map<String, Tiers> current, final String name) {
		if (current.size() == 0) { return null; }
		final SortedMap<String, Tiers> s = ((TreeMap<String, Tiers>) current);
		if (name.compareTo(s.lastKey()) > 0) { return null; }
		final Collection<Map.Entry<String, Tiers>> result = new ArrayList<Map.Entry<String, Tiers>>();
		for (final Map.Entry<String, Tiers> me : s.tailMap(name).entrySet()) {
			if (me.getKey().startsWith(name)) {
				result.add(me);
			} else {
				break;
			}
		}
		return result.size() > 0
				? result
				: null;
	}
}
